package com.LeeCode;

/**
 * 乘法表中第k小的数
 */

public class Code668 {
    public static void main(String[] args) {
        System.out.println(new Code668().findKthNumber(2, 3, 6));
    }

    public int findKthNumber(int m, int n, int k) {
        int left = 0, right = m * n;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (count(m, n, mid) >= k)
                right = mid;
            else
                left = mid;
        }
        return right;
    }

    private int count(int m, int n, int num) {
        int count = 0;
        for (int i = 1; i <= m; i++) {
            if (i > num) break;
            count += Math.min(num / i, n);
        }
        return count;
    }
}
